package com.cat.greedyAlgorithm;

import java.util.Arrays;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/two-city-scheduling/description/
 * @create 2025/8/25 16:18
 * @since JDK17
 */

public class Solution36 {
    public int twoCitySchedCost(int[][] costs) {
        Arrays.sort(costs, (o1, o2) -> Math.abs(o2[0] - o2[1]) - Math.abs(o1[0] - o1[1]));
        int ans = 0, a = 0, b = 0, n = costs.length;
        for (int i = 0; i < n; i++) {
            if (a < n / 2 && costs[i][0] < costs[i][1]) {
                a++;
                ans += costs[i][0];
            } else {
                b++;
                ans += costs[i][1];
            }
        }
        return ans;
    }
}
